package com.buddy.learn.algorithm.simple;

/**
 * 合并两个排序的链表
 *
 * @author Buddy
 * @date 2021/4/21
 */
public class ListNode_Merge {

    private static ListNode merge(ListNode list1, ListNode list2) {
        // 两个链表有空的话，直接返回另外一个链表
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }

        // 递归方式
        ListNode newHead;
        if (list1.data < list2.data) {
            newHead = list1;
            newHead.next = merge(list1.next, list2);
        } else {
            newHead = list2;
            newHead.next = merge(list1, list2.next);
        }
        // 最终结果
        return newHead;
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode b = new ListNode(3);
        ListNode c = new ListNode(5);
        ListNode d = new ListNode(7);
        ListNode e = new ListNode(9);
        ListNode f = new ListNode(10);
        head.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = f;

        ListNode head1 = new ListNode(2);
        ListNode b1 = new ListNode(4);
        ListNode c1 = new ListNode(5);
        ListNode d1 = new ListNode(6);
        ListNode e1 = new ListNode(8);
        ListNode f1 = new ListNode(11);
        head1.next = b1;
        b1.next = c1;
        c1.next = d1;
        d1.next = e1;
        e1.next = f1;
        ListNode merge = merge(head, head1);
        while (merge != null) {
            System.out.print(merge.data + " ");
            merge = merge.next;
        }
    }

    private static class ListNode {
        int data;
        ListNode next;

        ListNode(int data) {
            this.data = data;
        }
    }
}
